package learn.sort.heap;

import learn.CommUtil;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        //int[] arr = CommUtil.arr(5);
        int[] arr = {4, 2, 2, 6, 0};
        int[] old = Arrays.copyOf(arr, arr.length);
        CommUtil.printArray("原数组", arr);
        process(arr);
        CommUtil.printArray("排序后", arr);
        CommUtil.check(old, arr);
    }

    /**
     * 堆排序
     * 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
     * 比如大根堆:弹出根节点,把数组中最后一个数放在根节点,然后heapify形成一个新的大根堆.这样依次弹出,放入数组,就完成了排序
     */
    public static void process(int[] arr) {
        //首先把数组变成大根堆O[n*logn]
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }
        // 1.把一个数组变成大根堆 O[n]
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        // 2.此时arr[0]为最大值,arr[0] 与 arr[length-1] 交互位置, 那么arr[length-1]就是最大值
        int rightIndex = arr.length - 1;
        while (rightIndex > 0) {
            CommUtil.swap(arr, 0, rightIndex--);
            heapify(arr, 0, rightIndex + 1);
        }


    }


    /**
     * 下沉
     *
     * @param arr
     * @param index
     * @param length
     */
    public static void heapify(int[] arr, int index, int length) {
        int left = 2 * index + 1;
        while (left < length) {
            int right = left + 1;
            //左右比
            int largest = (arr[left] > arr[right] || right >= length ) ? left : right;
            //上下比
            largest = arr[index] > arr[largest] ? index : largest;
            //
            if (largest == index) {
                break;
            }
            CommUtil.swap(arr, index, largest);
            index = largest;
            left = 2 * index + 1;

        }
    }

    /**
     * 上升
     *
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        int father = -1;
        while (arr[index] > arr[father = (index - 1) / 2]) {
            CommUtil.swap(arr, index, father);
            index = father;
        }
    }
}
